1. Field of Invention
The present invention relates generally to mass digital data storage systems. More particularly, the present invention relates to systems and methods for efficiently enabling a plurality of physical blocks associated with a common logical block to be substantially resolved into a single physical block.
2. Description of the Related Art
The use of non-volatile memory systems such as flash memory storage systems is increasing due to the compact physical size of such memory systems, and the ability for non-volatile memory to be repetitively reprogrammed. The compact physical size of flash memory storage systems facilitates the use of such storage systems in devices which are becoming increasingly prevalent. Devices which use flash memory storage systems include, but are not limited to, digital cameras, digital camcorders, digital music players, handheld personal computers, and global positioning devices. The ability to repetitively reprogram non-volatile memory included in flash memory storage systems enables flash memory storage systems to be used and reused.
In general, flash memory storage systems may include flash memory cards and flash memory chip sets. Flash memory chip sets generally include flash memory components and a controller components. Typically, a flash memory chip set may be arranged to be assembled into an embedded system. The manufacturers of such assemblies or host systems typically acquire flash memory in component-form, as well as other components, then assemble the flash memory and the other components into a host system.
Within a file system associated with a flash memory system, memory is effectively divided into a system or directory area and a data area. The system area generally includes root directories and file allocation tables (FATs), while data files are typically included in the data area. A file system may write data in sectors, e.g., one page at a time, into physical blocks associated with the system area, while writing data in clusters, e.g., multiple pages at a time, into the data area.
Any updates associated with a logical block, or a block that is associated with a file system, are effectively propagated to a physical block which is mapped to the logical block. When the physical block which is mapped to the logical block is full, or is otherwise unable to accept an update, then a spare physical block is generally obtained, and the most recent data associated with the logical block is either copied, e.g., directly copied from the current physical block, or merged, e.g., substantially copied along with the update, into the spare physical block.
FIG. 1 is a diagrammatic representation of a logical block, a current physical block that is associated with the logical block, and a spare physical block that is to replace the current physical block. A logical block 200 is mapped to a physical block 210. Specifically, contents associated with pages 202 within logical block 200 are stored in a data area of pages 212 of physical block 210 as contents 214. When pages 212 within physical block 210 are full (as shown), or are otherwise unable to accept an update associated with logical block 200, a new or spare physical block 220, which includes pages 222, may be obtained, as for example from a set of spare blocks. The most recent contents 214 stored in physical block 210, along with any updates associated with logical block 200 that are not stored into physical block 210, may be copied into physical block 220 such that physical block 220 is effectively an up-to-date physical representation of logical block 200.
At times, interruptions may occur during the course of copying or merging contents 214 from physical block 210 into physical block 220 which cause the copying or merging process to be aborted and, as a result, incomplete. By way of example, power to a non-volatile memory device which includes physical blocks 210, 220 may be lost before the completion of a copying or merging process. When power is lost before the completion of a copying or merging process, some data associated with contents 210 may be lost.
To minimize the amount of data that may be lost as a result of an interrupted copying or merging process, physical block 210 and physical block 220 may be studied to determine which of physical block 210 and physical block 220 is an old physical block and which is a new, unfinished physical block. As will be understood by those skilled in the art, when a copying or merging process is interrupted, it may be time-consuming and difficult to determine whether physical block 210 or physical block 220 is intended to be the new physical block that contains up-to-date contents and is to be associated with logical block 200.
In order to facilitate a determination of which of two physical blocks may be intended to be the new physical block that is associated with a given logical block, flags are often implemented for use with the physical blocks. One method of implementing flags for use with physical blocks is described in U.S. Pat. No. 6,115,785, which is incorporated herein by reference in its entirety. Although the use of flags may be useful in enabling physical blocks which are in a copying or a merging process to be identified, it is often difficult to determine which of two physical blocks is a newer physical block and which is an older physical block. In addition, the use of flags often requires a partial write process when identifying physical blocks as being in either a copying or a merging process.
Therefore, what is desired is a process and a system which enables data to be efficiently restored when a copying or a merging process performed on physical blocks is interrupted before completion. That is, what is needed is a method and an apparatus for efficiently enabling a determination to be made as to which of a plurality of physical blocks is a new physical block that is intended to correspond to a particular logical block, and for enabling the most up-to-date data associated with the logical block to be provided to the new physical block.